package cn.edu.fzu.homemaking.dfa;

import java.util.*;

import org.apache.commons.lang3.StringUtils;
import org.springframework.util.CollectionUtils;

final class DfaTree {

    // root 节点为虚拟节点, 其值没有意义
    private DfaNode root = new DfaNode('*', false);

    DfaTree(Collection<String> keywords) {

        if (CollectionUtils.isEmpty(keywords)) {
            return;
        }

        for (String keyword : keywords) {
            if (StringUtils.isEmpty(keyword)) {
                continue;
            }

            DfaNode current = root;
            int length = keyword.length();
            int last = length - 1;
            for (int i = 0; i < length; i++) {
                current = current.addLeaf(new DfaNode(keyword.charAt(i), i == last));
            }
        }
    }


    /**
     * 字典树匹配
     * 
     * @param text 要匹配的源字符串
     * @param returnString 是否返回匹配到的词
     * @return
     */
    DfaResult match(String text, boolean returnString) {

        if (StringUtils.isEmpty(text)) {
            return DfaResult.NOT_MATCH;
        }

        DfaNode node = null;

        int start = -1;
        int length = text.length();

        Set<String> match = new HashSet<>();

        for (int i = 0; i < length; i++) {
            char key = text.charAt(i);

            if (node == null) {
                node = root;
            }

            node = node.getLeaf(key);

            if (node == null) {
                // 匹配失败, 如果已经在某个词上有了部分匹配, 要将游标回退到进入匹配的位置
                if (start != -1) {
                    i = start;
                    start = -1;
                }
            } else {
                // 部分匹配中, 记录下进入匹配的游标位置
                if (start == -1) {
                    start = i;
                }
                if (node.isEnd()) {
                    match.add(text.substring(start, i + 1));
                }
            }
        }
        if (!match.isEmpty()) {
            return returnString ? new DfaResult(match) : DfaResult.ONLY_MATCH;
        }
        return DfaResult.NOT_MATCH;
    }


    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        root.draw(sb, "");
        return sb.toString();
    }
}
